Plotkin bound

In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a limit (or bound) on the maximum possible number of codewords in binary codes of given length n and given minimum distance d.

1 Statement of the bound
2 Proof of case i
3 See also
4 References

Statement of the bound

A code is considered "binary" if the codewords use symbols from the binary alphabet $\{0,1\}$ . In particular, if all codewords have a fixed length n, then the binary code has length n. Equivalently, in this case the codewords can be considered elements of vector space $\mathbb{F}_2^n$ over the finite field $\mathbb{F}_2$ . Let $d$ be the minimum distance of $C$ , i.e.

$d = \min_{x,y \in C, x \neq y} d(x,y)$

where $d(x,y)$ is the Hamming distance between $x$ and $y$ . The expression $A_{2}(n,d)$ represents the maximum number of possible codewords in a binary code of length $n$ and minimum distance $d$ . The Plotkin bound places a limit on this expression.

Theorem (Plotkin bound):

i) If $d$ is even and $2d > n$ , then

$A_{2}(n,d) \leq 2 \left\lfloor\frac{d}{2d-n}\right\rfloor.$

ii) If $d$ is odd and $2d%2B1 > n$ , then

$A_{2}(n,d) \leq 2 \left\lfloor\frac{d%2B1}{2d%2B1-n}\right\rfloor.$

iii) If $d$ is even, then

$A_{2}(2d,d) \leq 4d.$

iv) If $d$ is odd, then

$A_{2}(2d%2B1,d) \leq 4d%2B4$

where $\left\lfloor ~ \right\rfloor$ denotes the floor function.

Proof of case i

Let $d(x,y)$ be the Hamming distance of $x$ and $y$ , and $M$ be the number of elements in $C$ (thus, $M$ is equal to $A_{2}(n,d)$ ). The bound is proved by bounding the quantity $\sum_{(x,y) \in C^2, x\neq y} d(x,y)$ in two different ways.

On the one hand, there are $M$ choices for $x$ and for each such choice, there are $M-1$ choices for $y$ . Since by definition $d(x,y) \geq d$ for all $x$ and $y$ ( $x\neq y$ ), it follows that

$\sum_{(x,y) \in C^2, x\neq y} d(x,y) \geq M(M-1) d.$

On the other hand, let $A$ be an $M \times n$ matrix whose rows are the elements of $C$ . Let $s_i$ be the number of zeros contained in the $i$ 'th column of $A$ . This means that the $i$ 'th column contains $M-s_i$ ones. Each choice of a zero and a one in the same column contributes exactly $2$ (because $d(x,y)=d(y,x)$ ) to the sum $\sum_{x,y \in C} d(x,y)$ and therefore

$\sum_{x,y \in C} d(x,y) = \sum_{i=1}^n 2s_i (M-s_i).$

If $M$ is even, then the quantity on the right is maximized if and only if $s_i = M/2$ holds for all $i$ , then

$\sum_{x,y \in C} d(x,y) \leq \frac{1}{2} n M^2.$

Combining the upper and lower bounds for $\sum_{x,y \in C} d(x,y)$ that we have just derived,

$M(M-1) d \leq \frac{1}{2} n M^2$

which given that $2d>n$ is equivalent to

$M \leq \frac{2d}{2d-n}.$

Since $M$ is even, it follows that

$M \leq 2 \left\lfloor \frac{d}{2d-n} \right\rfloor.$

On the other hand, if $M$ is odd, then $\sum_{i=1}^n 2s_i (M-s_i)$ is maximized when $s_i = \frac{M \pm 1}{2}$ which implies that

$\sum_{x,y \in C} d(x,y) \leq \frac{1}{2} n (M^2-1).$

Combining the upper and lower bounds for $\sum_{x,y \in C} d(x,y)$ , this means that

$M(M-1) d \leq \frac{1}{2} n (M^2-1)$

or, using that $2d > n$ ,

$M \leq \frac{2d}{2d-n} - 1.$

Since $M$ is an integer,

$M \leq \left\lfloor \frac{2d}{2d-n} - 1 \right\rfloor = \left\lfloor \frac{2d}{2d-n} \right\rfloor -1 \leq 2 \left\lfloor \frac{d}{2d-n} \right\rfloor.$

This completes the proof of the bound.

References

Binary codes with specified minimum distance, M. Plotkin, IRE Transactions on Information Theory, 6:445-450, 1960. doi:10.1109/TIT.1960.1057584

Plotkin bound

Contents

Statement of the bound

Proof of case i

See also

References